Masala #0616

Xotira 64 MB Vaqt 2000 ms Qiyinchiligi 66 %
14

  

Shahzodga yordam

Shahzod o'z ishini yaxshi ko'radi, lekin u ofisiga borish va qaytib kelish uchun ortiqcha vaqt sarflashni yoqtirmaydi. Ko'p yillar davomida ishlagandan so'ng, u oddiy kunlarda ofisiga boradigan eng qisqa masofani biladi.

Yaqinda shaharda turli yo‘llarni muntazam ta’mirlash ishlari boshlandi. Har kuni yo'l to'sib qo'yiladi va o'sha kuni undan hech kim foydalana olmaydi, lekin boshqa barcha yo'llardan foydalanish mumkin.Har kuni siz uning ofisiga borishi mumkin bo'lgan minimal masofani aniqlashingiz kerak.


Kiruvchi ma'lumotlar:

0 dan \(N-1\) gacha raqamlangan \(N\) ta shahar va \(M\) ikki yoʻnalishli yoʻllar mavjud.

Kirishning birinchi qatorida ikkita \(N, M (1 < N, M < 100000)\)
\(M\) qatorlar bo'lib, ularning har biri bo'shliqdan ajratilgan uchta \(u,v(0 \le u,v \le N−1), w(0 < w < 1001)\)
Keyingi qatorda ikkita son \(S,D( 0 \le S,D < N)\). \(S\) - Shahzod yashaydigan shahar va \(D\) - uning idorasi joylashgan shahar.
Keyingi qatorda \(Q ( 0 < Q < 21 )\)
\(Q\) satrlardan keyin har birida ikkita \(u_1\) va \(v_1\) butun sonlari mavjud bo'lib,o'sha kuni \(u_1\) va \(v_1\) o'rtasidagi yo'l to'sib qo'yilgan.


Chiquvchi ma'lumotlar:

Shahzod borishi mumkin bo'lgan minimal masofani chiqaring (Har bir test uchun alohida). Agar yo'l bo'lmasa, -1 ni chop eting.


Misollar
# input.txt output.txt
1
4 5
0 1 2
1 2 3
2 3 5
0 3 13
1 3 10
0 3
2
1 2
0 3
12
10
Yechimini yuborish
Bu amalni bajarish uchun tizimga kiring, agar profilingiz bo'lmasa istalgan payt ro'yxatdan o'tishingiz mumkin